const mergeRecursion = (left: number[], right: number[]) => {
    let i = 0;
    let j = 0;
    let result: number[] = [];

    while(i < left.length && j < right.length) {
      result.push(left[i] < right[j] ? left[i++] : right[j++]);
    }
    return result.concat(i >= left.length ? right.slice(j) : left.slice(i));
};

export const sortMergeRecursion = (array: number[]): number[] => {
  const length = array.length;
  const half = Math.ceil(length / 2);
  let arr: number[] = array;
  
  if (array.length > 1) {
    let left = sortMergeRecursion(array.slice(0, half));
    let right = sortMergeRecursion(array.slice(half));
    arr = mergeRecursion(left, right);
  }
  
  return arr;
};

export const sortMergeLoop = (array: number[]) => {
  let result: number[][]  = [];

  for (let i = 0; i < array.length; i++) {
    result.push([array[i]]);
  }

  if (array.length % 2) {
    result.push([]);
  }

  while(result.length > 1) {
    const r: number[][] = [];
    for (let i = 0; i < result.length; i = i + 2) {
      let j = 0;
      let k = 0;
      let left = result[i] || [];
      let right = result[i + 1] || [];
      let rItem: number[] = [];
      
      while(j < left.length && k < right.length) {
        if (left[j] < right[k]) {
          rItem.push(left[j++]);
        } else {
          rItem.push(right[k++]);
        }
      }
      rItem = rItem.concat(j < left.length ? left.slice(j) || [] : right.slice(k) || []);
      r.push(rItem);
    }
    result = r;
  }

  return result?.[0];
};
